題目： 217. Contains Duplicate

連結：https://leetcode.com/problems/contains-duplicate/description/

• 等級：Easy

解題思路

有效的方法是使用Hash資料結構來儲存遇到的元素。 統計數組時，如果Hash集中已存在某個元素，則傳回 true。 否則，將該元素新增至Hash集中。 如果循環完成後沒有發現任何重複項，則傳回 false。

class Solution {
    public boolean containsDuplicate(int[] nums) {
        HashSet<Integer> save = new HashSet<Integer>();
        for (int i = 0; i < nums.length;i++)
        {
            if (save.contains(nums[i]))
                return true;
            else
                save.add(nums[i]);
        }
        return false;
    }
}

• Time complexity: O(n)
• Space complexity: O(n)

題目：1. Two Sum

連結：https://leetcode.com/problems/two-sum/description/

• 等級：Easy

解題思路

1. 建立一個空的Hash表來儲存元素和它們的索引。
2. 從左到右遍歷數組。
3. 對於每個元素 nums[i]，計算差值，方法是將目標減去它：差值 = 目標 - nums[i]。
4. 檢查差值是否存在於Hash表中。如果存在，則找到了一個解決方案。
5. 如果差值不存在於Hash表中，將當前元素 nums[i] 添加到Hash表中，其索引作為值。
6. 重複步驟 3-5，直到找到解決方案或達到數組的末尾。
7. 如果找不到解決方案，返回一個空數組。

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer,Integer> save = new HashMap<Integer,Integer>();
        for (int i = 0; i < nums.length;i++)
        {
            int val = target - nums[i];
            if (save.containsKey(val))
                return new int[] {i,save.get(val)};
            else
                save.put(nums[i],i);
        }
        return new int[]{};
    }
}

• Time complexity: O(n)
• Space complexity: O(1)